\subsection{Ramsey's theorem}
Macroscopically, theorems in Ramsey theory are of the form `complete disorder in sufficiently large systems is impossible'.
\begin{proposition}
	Let \( c \) be a 2-edge (not proper) colouring of \( K_6 \).
	Then there exists a monochromatic triangle \( K_3 \); there exists a subgraph induced on three vertices where all edges have the same colour.
\end{proposition}
\begin{proof}
	Suppose our colours are red and blue.
	Let \( x \in V(K_6) \).
	Without loss of generality, \( x \) has three neighbours \( y_1, y_2, y_3 \) coloured red.
	Then the edges between the \( y_i \) cannot be coloured red.
	So they must all be coloured blue, but then this forms a blue triangle.
\end{proof}
\begin{definition}
	Let \( s \geq 2 \).
	Then the \emph{\( s \)th Ramsey number}, denoted \( R(s) \), is the minimal \( n \) such that every 2-edge colouring of \( K_n \) contains a monochromatic \( K_s \).
\end{definition}
It is not clear \emph{a priori} that such numbers indeed exist.
\begin{definition}
	Let \( s, t \geq 2 \).
	We define \( R(s,t) \) be the minimal \( n \) such that every 2-edge colouring of \( K_n \) contains either a red \( K_s \) or a blue \( K_t \).
\end{definition}
\begin{remark}
	\( R(s, t) \) is symmetric, and \( R(s) = R(s,s) \).
	Note that \( R(2,t) \) is the minimal \( n \) that contains a red edge or \( K_t \), so \( R(2,t) = t \).
	We showed above that \( R(3,3) = R(3) \leq 6 \), and in fact this is an equality by demonstrating a 2-edge colouring of \( K_5 \) containing no monochromatic triangle.
\end{remark}
\begin{theorem}[Ramsey]
	For all \( s, t \), the Ramsey number \( R(s, t) \) exists, and \( R(s,t) \leq R(s-1,t) + R(s,t-1) \).
\end{theorem}
\begin{proof}
	Apply induction on \( s + t \).
	For \( s, t \leq 2 \), the result holds.
	Now suppose \( s, t > 2 \), and let \( a = R(s-1,t), b = R(s,t-1) \).
	Let \( n = a + b = R(s-1,t) + R(s,t-1) \), and consider the complete graph \( K_n \).
	Let \( c \colon E(K_n) \to \qty{\text{red, blue}} \) be a given colouring.

	Let \( x \in K_n \), and let \( N_r(x) \) be the red neighbourhood and \( N_b(x) \) be the blue neighbourhood.
	Suppose that \( \abs{N_r(x)} \geq a \).
	In this case, \( N_r(x) \) contains either a red \( K_{s-1} \), in which case \( N_r(x) \cup \qty{x} \) is a red \( K_s \) in \( K_n \); or a blue \( K_t \), in which case we are already done.
	Now suppose \( \abs{N_b(x)} \geq b \).
	Then \( N_b(x) \) contains either a red \( K_s \) in which case we are done; or it contains a blue \( K_{t-1} \), in which case \( N_b(x) \cup \qty{x} \) is a blue \( K_t \) in \( K_n \) as required.
	Suppose that neither of these cases occur, so \( \abs{N_r(x)} \leq a - 1 \) and \( \abs{N_b(x)} \leq b - 1 \), so \( \abs{N(x)} \leq a + b - 2 \), which is a contradiction since the graph is complete.
\end{proof}
\begin{corollary}
	For all \( s \), the Ramsey number \( R(s) \) exists.
\end{corollary}
\begin{definition}
	\( R_k(s_1, \dots, s_k) \) is the minimal \( n \) such that every \( k \)-edge colouring of \( K_n \) contains a \( K_{s_i} \) coloured \( i \) for some \( i \).
\end{definition}
\begin{theorem}[multicoloured Ramsey's theorem]
	For \( s_1, \dots, s_k \) for \( k \geq 2 \), then \( R_k(s_1, \dots, s_k) \) exists.
\end{theorem}
\begin{proof}
	We will show by induction on \( k \) that \( R_k(s_1, \dots, s_k) \leq R(s_1, R_{k-1}(s_2, \dots, s_k)) = n \).
	Let \( c \) be a \( k \)-colouring of \( K_n \).
	Apply the two-colour version of Ramsey's theorem to obtain either a \( K_{s_1} \) coloured \( 1 \), or a \( K_{R_{k-1}(s_2, \dots, s_k)} \) coloured in any combination of \( 2, \dots, k \).
	If we have a \( K_{s_1} \) coloured \( 1 \), we are done.
	Otherwise, apply induction to obtain an edge colouring of \( K_{R_{k-1}(s_2, \dots, s_k)} \) to obtain a \( K_{s_i} \) coloured \( i \) for some \( i \geq 2 \).
\end{proof}
\begin{remark}
	We have seen \( R(3) = 6 \).
	There are very few known Ramsey numbers.
	\( R(4) = 18 \), but \( R(5) \) is unknown.
\end{remark}

\subsection{Infinite graphs and larger sets}
\begin{theorem}
	Let \( c \) be a 2-colouring of the countably infinite complete graph, so \( c \colon \mathbb N^{(2)} \to \qty{\text{red, blue}} \).
	Then there exists an infinite set \( X \subseteq \mathbb N \) which is monochromatic, so \( X^{(2)} \) is coloured either entirely red or entirely blue.
\end{theorem}
\begin{remark}
	The finite version of Ramsey's theorem cannot be applied here; we can create arbitrarily large cliques, but we do not know if such cliques connect into an infinite set.
\end{remark}
\begin{proof}
	We construct a sequence \( x_1, x_2, \dots \) inductively as follows.
	Let \( x_1 \in \mathbb N \) be arbitrary.
	\( x_1 \) has either an infinite red neighbourhood or an infinite blue neighbourhood.
	We define \( S_1 \) to be the red neighbourhood of \( x_1 \) if it is infinite, or the blue neighbourhood otherwise, so \( S_1 \) is infinite.
	Now let \( x_2 \in S_1 \).
	Now, \( x_2 \) has either an infinite red neighbourhood in \( S_1 \) or an infinite blue neighbourhood in \( S_1 \), so we can define \( S_2 \) to be one of these that is infinite, and proceed inductively.

	For each \( i \), all edges \( x_i \sim x_j \) where \( i < j \) have the same colour by construction.
	Label a vertex red if all its forward-facing edges are red, and label an edge blue if all its forward-facing edges are blue.
	Then there are either infinitely many red vertices or infinitely many blue vertices.
	Without loss of generality, suppose the set of red vertices \( X \) is infinite.
	Then all edges in \( X \) are coloured red, so \( X \) is the infinite monochromatic set as required.
\end{proof}
\begin{remark}
	We can easily construct a version of the above theorem for an arbitrary finite amount of colours, using the same idea as from the multiple-colour version of Ramsey's theorem in the finite case.
\end{remark}
\begin{example}
	It can be difficult to determine which colour has an infinite monochromatic clique.
	Suppose we colour \( ij \) with the maximal \( n \) such that \( 2^n \mid i + j \), modulo 2.
	The set \( \qty{2^2, 2^4, 2^6, \dots} \) is an example of an infinite monochromatic clique.

	Suppose \( ij \) is coloured with the number of distinct prime factors of \( i + j \), modulo 2.
	The colour of the infinite clique is not known.
\end{example}
\begin{remark}
	It is possible to deduce the existence of \( R(s,t) \) from the infinite version.
\end{remark}
\begin{theorem}
	Let \( c \) be a 2-colouring of the set of \( r \)-sets of \( \mathbb N \), so \( c \colon \mathbb N^{(r)} \to \qty{\text{red, blue}} \).
	Then there exists an infinite set \( X \subseteq \mathbb N \) such that \( X^{(r)} \) is monochromatic.
\end{theorem}
\begin{proof}
	Apply induction on \( r \).
	If \( r = 2 \), we fall back to the previous theorem.
	We define a sequence \( x_1, x_2, \dots \) and a sequence of infinite sets \( S_1, S_2, \dots \) by the following procedure.
	We start by choosing \( x_1 \) arbitrarily.
	Now, consider the colouring \( c_{x_1}(F) = c(\qty{x_1} \cup F) \) for \( F \in (\mathbb N \setminus \qty{x_1})^{(r-1)} \).
	By induction, there exists a set \( S_1 \subseteq \mathbb N \setminus \qty{x_1} \) that is infinite and \( S_1^{(r-1)} \) is monochromatic with respect to the colouring \( c_{x_1} \).
	Now we choose \( x_2 \in S_1 \), and proceed inductively.

	The sequence \( x_1, x_2, \dots \) has the property that \( F_i = \qty{\qty{x_{i_1}, \dots, x_{i_r}} \mid i_1 < \dots < i_r} \) are monochromatic for each \( i \).
	But there are either infinitely many red-coloured \( x_i \) or infinitely many blue-coloured \( x_i \).
	Let \( X \) be one of these infinite sets, then \( X^{(r)} \) is monochromatic.
\end{proof}
We can produce a similar version of this theorem for the finite case, along with an explicit inductively-defined bound.
\begin{definition}
	Let \( r \in \mathbb N \), and \( s, t \geq 1 \).
	We define the \emph{\( r \)-set Ramsey number} \( R^{(r)}(s,t) \) to be the minimal \( n \) such that for every 2-colouring of \( \qty{1, \dots, n}^{(r)} \), it contains either a set \( S \) with \( \abs{S} = s \) and \( S^{(r)} \) are coloured red, or a set \( T \) with \( \abs{T} = t \) and \( T^{(r)} \) are coloured blue.
\end{definition}
\begin{remark}
	\( R^{(1)}(s,t) = s + t - 1 \).
	\( R^{(2)}(s,t) = R(s,t) \).
	\( R^{(r)}(r,t) = t = R^{(r)}(t,r) \).
\end{remark}
\begin{theorem}
	For all \( r, s, t \geq 1 \), the number \( R^{(r)}(s,t) \) exists.
\end{theorem}
\begin{proof}
	Apply induction on \( r \), and then induction on \( s + t \).
	If \( s \leq r \) or \( t \leq r \), we are done, since \( R^{(r)}(r,t) = t \).
	We claim that \( R^{(r)}(s,t) \leq R^{(r-1)}(R^{(r)}(s-1,t) + R^{(r)}(s,t-1)) + 1 = N \).

	Consider a 2-coloured set \( \qty{1, \dots, n}^{(r)} \) where \( n \geq N \).
	Choose a vertex \( x \in \qty{1, \dots, n} \).
	Consider the colouring \( c_x(F) = c(\qty{x} \cup F) \) where \( F \in (\qty{1, \dots, n} \setminus \qty{x})^{(r-1)} \).
	Applying induction on \( r \), we have a set \( S_1 \) such that \( \abs{S_1} = R^{(r)}(s-1,t) \) and \( S_1^{(r-1)} \) is red, or there is a set \( S_2 \) with \( \abs{S_2} = R^{(r)}(s,t-1) \) and \( S_2^{(r-1)} \) is blue.
	We consider the first case; the other is similar.

	Apply the \( r \)-set version of Ramsey's theorem by induction to \( S_1 \) to find either a set \( A \subseteq S_1 \) with \( \abs{A} = s - 1 \) and \( A^{(r)} \) is coloured red (with respect to \( c \)), or a set \( B \subseteq S_2 \) with \( \abs{B} = t \) and \( B^{(r)} \) is coloured blue.
	If \( B \) exists, we are done.
	If \( A \) exists, \( A \cup \qty{x} \) is coloured red and has size \( s \) as required.
\end{proof}

\subsection{Upper bounds}
\begin{proposition}
	Let \( s, t \geq 2 \), we have \( R(s,t) \leq \binom{s+t-2}{t-1} \).
	In particular, \( R(s) = R(s,s) \leq 4^s \).
\end{proposition}
\begin{proof}
	Apply induction on \( s + t \).
	We know \( R(s,2) = s = \binom{s+2-2}{2-1} \) as required.
	Suppose this holds for \( R(s-1,t) \) and \( R(s,t-1) \).
	We have already shown that \( R(s,t) \leq R(s-1,t) + R(s,t-1) \).
	So
	\[ R(s,t) \leq R(s-1,t) + R(s,t-1) \leq \binom{s+t-2}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1} \]
\end{proof}
We are interested in bounding \( R^{(r)}(s,t) \).
Note that we have the bound \( R^{(r)}(s,t) \leq R^{(r-1)}(R^{(r)}(s,t-1), R^{(r)}(s-1,t)) + 1 \).
Define \( f_1(x) = 2x \), and recursively, \( f_n(x) = f_{n-1}^x(x) \).
Then \( f_2(x) \sim 2^x \), and as \( n \) increases, \( f_n \) increases very rapidly.
So our bound on \( R^{(r)}(s,t) \) grows asymptotically on the order of \( f_r(s+t) \).

\subsection{Lower bounds}
We can explicitly construct some lower bounds for \( R(s) \).
\begin{proposition}
	\( R(s) > (s-1)^2 \).
\end{proposition}
\begin{proof}
	Consider the graph defined by \( (s-1) \) disjoint \( K_{s-1} \) cliques, all of which are coloured blue, but all lines between cliques are coloured red.
	This graph has no monochromatic \( K_s \).
\end{proof}
\begin{theorem}[Erd\H{o}s]
	Let \( s \geq 3 \).
	Then \( R(s) \geq 2^{\frac s2} \).
\end{theorem}
\begin{proof}
	Consider \( G = K_n \) for \( n \leq 2^{\frac s 2} \).
	For each edge \( e \) in \( G \), we construct an independent Bernoulli random variable \( X_e \) with parameter \( \frac 12 \).
	If \( X_e = 0 \), we colour \( e \) red, and if \( X_e = 1 \), we colour \( e \) blue.
	Then
	
	\begin{align*}
		\prob{\text{colouring has a monochromatic } K_s} &= \prob{\bigcup_{K \in \qty{1, \dots, n}^{(s)}} \qty{K \text{ monochromatic}}} \\
		&\leq \sum_{K \in \qty{1, \dots, n}^{(s)}} \prob{K \text{ monochromatic}} \\
		&= \sum_{K \in \qty{1, \dots, n}^{(s)}} 2 \cdot 2^{-\binom s 2} \\
		&= \binom n s 2 \cdot 2^{-\binom s 2} \\
		&< \frac{n^s}{s!} 2 \cdot 2^{-\frac{s(s-1)}{2}} \\
		&= 2 \qty(\frac{n}{(s!)^{\frac 1s}} 2^{-\frac{s-1}{2}})^s \\
		&\leq 2 \qty( \frac{2^{\frac 12}}{(s!)^{\frac 1s}} )^s
	\end{align*}
	Note that \( s! \geq 2^{\frac s 2 + 1} \), so \( (s!)^{\frac 1s} \geq 2^{\frac 12 + \frac 1s} \).
	\[ \prob{\text{colouring has a monochromatic } K_s} < 2 \qty(\frac{1}{2^{\frac 1s}})^s \leq 1 \]
	Since the probability is less than 1, there must exist a colouring that has no monochromatic \( K_s \).
\end{proof}
\begin{remark}
	We can think about this proof as follows.
	Consider the collection of \( 2^{\binom n 2} \) colourings of \( K_n \).
	Then for each clique, there are at most \( 2^{\binom n 2} \cdot 2 \cdot 2^{-\binom s 2} \) colourings where that clique is monochromatic.
	So the collection of all colourings where none of these cliques are monochromatic has at least as many elements as \( 2^{\binom n 2} - \binom n 2 2^{\binom n 2} \cdot 2 \cdot 2^{-\binom s 2} \).
	In general, however, a probabilistic interpretation is more powerful.
\end{remark}
\begin{remark}
	This proof is nonconstructive.
	It is a major open problem to explicitly construct colourings to show that \( R(s) > (1 + \varepsilon)^s \).
\end{remark}
